
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    int translateNum( int num ) {
        if ( num == 0 ) {
            return 1;
        }

        vector< int > nums;

        while ( num != 0 ) {
            nums.push_back( num % 10 );
            num /= 10;
        }
        std::reverse( nums.begin(), nums.end() );

        int dp1 = 1, dp2 = 1;
        int temp = 0;
        for ( size_t i = 1; i < nums.size(); i++ ) {
            temp = dp2;
            if ( nums[ i - 1 ] * 10 + nums[ i ] < 26 && ( nums[ i - 1 ] == 1 || nums[ i - 1 ] == 2 ) ) {
                dp2 = dp1 + dp2;
            }
            dp1 = temp;
        }

        return dp2;
    }

    int movingCount( int m, int n, int k ) {
        vector< vector< bool > > access( m, vector< bool >( n, false ) );

        dfs( access, 0, 0, k );

        int result = 0;

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                access[ i ][ j ] ? result++ : result;
            }
        }
        return result;
    }

    // 剑指 Offer 59 - I. 滑动窗口的最大值
    vector< int > maxSlidingWindow( vector< int >& nums, int k ) {
        vector< int > res;
        deque< int >  max;

        for ( int i = 0; i < k; i++ ) {
            while ( !max.empty() && max.back() < nums[ i ] ) {
                max.pop_back();
            }
            max.emplace_back( nums[ i ] );
        }
        res.push_back( max.front() );

        for ( size_t i = k; i < nums.size(); i++ ) {
            if ( max.front() == nums[ i - k ] ) {
                max.pop_front();
            }
            while ( !max.empty() && max.back() < nums[ i ] ) {
                max.pop_back();
            }
            max.emplace_back( nums[ i ] );
            res.push_back( max.front() );
        }
        return res;
    }

private:
    inline int sumBit( int num, int num2 ) {
        int result = 0;
        while ( num > 0 ) {
            result += num % 10;
            num /= 10;
        }

        while ( num2 > 0 ) {
            result += num2 % 10;
            num2 /= 10;
        }

        return result;
    }

    void dfs( vector< vector< bool > >& a, size_t i, size_t j, int k ) {

        if ( i >= a.size() || j >= a.front().size() || a[ i ][ j ] == true || sumBit( i, j ) > k ) {
            return;
        }
        a[ i ][ j ] = true;
        dfs( a, i, j + 1, k );
        dfs( a, i + 1, j, k );
    }
};

// 剑指 Offer 41. 数据流中的中位数
class MedianFinder {
public:
    MedianFinder() {}

    void addNum( int num ) {

        lowQueue.push( num );
        highQueue.push( lowQueue.top() );
        lowQueue.pop();

        if ( highQueue.size() > lowQueue.size() ) {
            lowQueue.push( highQueue.top() );
            highQueue.pop();
        }
    }

    double findMedian() {
        if ( highQueue.empty() ) {
            return lowQueue.top();
        }
        if ( ( lowQueue.size() + highQueue.size() ) % 2 == 0 ) {
            return ( lowQueue.top() + highQueue.top() ) / 2.0;
        }
        else {
            return lowQueue.top();
        }
    }

private:
    priority_queue< int, vector< int >, greater< int > > highQueue;  // 小顶堆
    priority_queue< int, vector< int >, less< int > >    lowQueue;   // 大顶堆
};
